package com.example.javamaday.leetcode;

import com.example.javamaday.leetcode.base.TreeNode;

public class LeetCodeTest0108 {

    public static void main(String[] args) {

    }


    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 1) {
            return new TreeNode(nums[0]);
        }
        if (nums.length == 2) {
            TreeNode node = new TreeNode(nums[0]);
            node.left = null;
            node.right = new TreeNode(nums[1]);
        }
        if (nums.length >= 3) {
            int middle = (nums.length) / 2;
            TreeNode treeNode = new TreeNode(nums[middle]);
            treeNode.left = sortedArrayToBst(nums, 0, middle);
            treeNode.right = sortedArrayToBst(nums, middle, nums.length - 1);
            return treeNode;
        }
        return null;
    }

    public TreeNode sortedArrayToBst(int[] nums, int start, int end) {
        if (end - start >= 3) {
            int middle = (start + end) / 2;
            TreeNode treeNode = new TreeNode(nums[middle]);
            treeNode.left = sortedArrayToBst(nums, start, middle);
            treeNode.right = sortedArrayToBst(nums, middle, end);
            return treeNode;
        }
        if (end - start == 2) {
            TreeNode treeNode = new TreeNode(nums[start + 1]);
            treeNode.left = new TreeNode(nums[start]);
            treeNode.right = new TreeNode(nums[end]);
            return treeNode;
        }
        if (end - start == 1) {
            TreeNode treeNode = new TreeNode(nums[start]);
            treeNode.left = null;
            treeNode.right = new TreeNode(nums[end]);
            return treeNode;
        }
        if (end == start) {
            TreeNode treeNode = new TreeNode(nums[start]);
            treeNode.left = null;
            treeNode.right = null;
            return treeNode;
        }
        return null;
    }
}
